Hashtable עבור JavaScript - מבנה נתונים יעיל לשליפה בסיבוכיות נמוכה 

לעיתים קרובות יש צורך במבנה נתונים שישמור פרמטרים שונים בצורה של מפתח-ערך (key-value).
מערך אסוציאטיבי (associative array) הוא פתרון שכזה. למרות מהירות גישה וחתימת זכרון נמוכה, איטרציה על האלמנטים ששמורים במערך בלתי אפשרית.

לאפליקציות שנכתבות לסביבת IE בלבד יש אפשרות להשתמש באובייקט המילון של מיקרוסופט (Dictionary object).
שימוש מסיבי באובייקט יכול לצור חתימת זכרון גבוהה וביצועים לא מזהירים (בלשון המעטה).

מאמר זה יציג פתרון אפשרי לבעיה, פתרון שמיושם באפליקציות הפועלות בסביבת אמת.

אובייקט Hashtable

הרעיון שעומד מאוחרי אובייקט זה הינו שימוש ביכולת מערך אסוציאטיבי ובמהירות הגישה אליו תוך הוספת יכולות נוספות. הממשק (interface) מזכיר את הממשק של אובייקטי Hash של שפת JAVA (Hashmap,Hashtable) ולא בכדי, ממשק זה נועד לתת גמישות מקסימלית באיחסון ואחזור המידע.

נתחיל בהגדרת המשתנים של המחלקה:

    Hashtable.prototype.hash = null;

    Hashtable.prototype.keys = null;

    Hashtable.prototype.location = null;

הגדרנו שלושה משתנים:

• hash - מערך אסוציטיבי שישמור את המידע.

• keys - מערך רגיל שמחזיק את המפתחות של המערך. נשתמש בו לכשנרצה לרוץ סידרתית על רשימת הערכים שלנו.

• location - מצביע על הערך הנוכחי.

אחרי הגדרת המשתנים, נגדיר את הפונקציה הבונה (constructor) של המחלקה:

function Hashtable(){

    this.hash = new Array();

    this.keys = new Array();



    this.location = 0;

}

פשוט וברור. נאתחל את שני המערכים שלנו ואת המצביע.

אחרי שסיימנו עם החלק ההגדרתי אפשר להתחיל לקודד...
שתי הפונקציות הראשונות שנכתוב הן get ו - put. אלו הם הפונקציות הראשיות לאחסון ולאחזור הנתונים.

להלן הגדרתן:

Hashtable.prototype.get = function (key)

    return this.hash[key];

}



Hashtable.prototype.put = function (key, value){

    if (value == null)

        return null;



    if (this.hash[key] == null)

        this.keys[this.keys.length] = key;



    this.hash[key] = value;

}

פונקציית get פשוט מחזירה את הערך מתוך המערך לפי המפתח שסופק לה, בעוד put נדרשת לבצע מעט יותר עבודה. דבר ראשון היא בודקת אם הערך ריק (null) אזי אין טעם להמשיך והתהליך נפסק (ע"מ למחוק ערך מהמערך קיימת הפונקציה remove שמבצעת את העבודה). לאחר מכן נבדק האם המפתח כבר מוגדר. אם כן אזי יש להחליף את הערך הישן בחדש ואם לא הוגדר מפתח כזה בעבר הרי שיש ליצור אותו ולמלא אותו בערך המתאים.

סדרה נוספת של פונקציות מאפשרת לנו לרוץ בצורה סדרתית על כל הערכים ששמורים לנו.
במקום להציג את הקוד עצמו, נציג כאן איך להגדיר, להשתמש ולרוץ על רשימה שכזו:

//declare an instance

var items = new Hashtable();



//add 3 values to the hash



items.put("key1", "value1");

items.put("key2", "value2");

items.put("key3", "value3");



//just show that all works well

alert(items.get("key2"));



//start iterating the hash

//Just to be on the safe side (maybe someone has used it before?)

items.moveFirst();

while (tems.next()){ //While we have more elements

    //print the key and the value

    alert (items.getKey() + " = " + items.getValue());

}

למחלקה Hashtable עוד כמה פונקציות מעניינות אותן נזכיר כאן בקצרה:

• add - מאפשר מיזוג בין שני אובייקטים של Hashtable.

• toString - מחזירה מחרוזת המתארת את המפתחות ואת הערכים המתאימים להם.


• getKeyOfValue - מחזירה את רשימת המפתחות שמכילים ערך מסויים.